﻿using System;
using System.Collections.Generic;

namespace QSharp.Scheme.Classical.Sequential
{
    public static class HeapSort
    {
        #region Nested types

        /// <summary>
        ///  AddToHeap removes an arbitrary node (in most cases,
        ///  the one at the head) from the list and adds it to
        ///  the end of a complete heap
        ///
        ///  ExrudeFromHeap squeezes out the root node and add it
        ///  to the list (whether the beginning or the end), and 
        ///  makes the end node of this complete heap temporarily
        ///  take the place
        /// </summary>
        public interface IHeapSortAdapter
        {
            Heap.IHeapNode AddToHeap(Heap.IHeap h);
            bool ExtrudeFromHeap(Heap.IHeap h);
        }

        /// <summary>
        ///  FillHeap loads the entire list onto the heap
        /// 
        ///  ExrudeFromHeap is the same as that of IHeapSortAdapter
        /// </summary>
        public interface IHeapSortAdapter2
        {
            void FillHeap(Heap.IListedHeap h);
            bool ExtrudeFromHeap(Heap.IHeap h);
        }

        #endregion

        #region Methods

        public static void Sort(Heap.IHeap h, IHeapSortAdapter ha, Comparison<Heap.IHeapNode> cmp)
        {
            Heap.IHeapNode n;

            while ((n = ha.AddToHeap(h)) != null)
            {
                Heap.Exalt(h, n, cmp);
            }

            while (ha.ExtrudeFromHeap(h))
            {
                Heap.Expel(h, h.Root, cmp);
            }
        }

        public static void Sort(Heap.IListedHeap h, IHeapSortAdapter2 ha, 
            Comparison<Heap.IHeapNode> cmp)
        {
            ha.FillHeap(h);

            for (Heap.IHeapNode n = h.GetLastNonLeaf(); n != null; n = h.GetPrevNodeLinearly(n))
            {
                Heap.Expel(h, n, cmp);
            }

            while (ha.ExtrudeFromHeap(h))
            {
                Heap.Expel(h, h.Root, cmp);
            }
        }

        #endregion
    }

    public class ListBasedHeap<T, TListOfT> : 
        Heap.IListedHeap, 
        HeapSort.IHeapSortAdapter, HeapSort.IHeapSortAdapter2
        where T : IComparable<T>
        where TListOfT : IList<T>
    {
        #region Nested types

        public class HeapNode : Heap.IHeapNode
        {
            public readonly int Index;
            
            public HeapNode(int index)
            {
                Index = index;
            }
        }

        #endregion

        #region Methods

        public ListBasedHeap(TListOfT list)
        {
            List = list;
            Head = 0;
        }

        public Heap.IHeapNode SwapUp(Heap.IHeapNode a, Heap.IHeapNode b)
        {
            var aa = a as HeapNode;
            var bb = b as HeapNode;
            System.Diagnostics.Trace.Assert(aa != null && bb != null);
            T t = List[aa.Index];
            List[aa.Index] = List[bb.Index];
            List[bb.Index] = t;
            return a;
        }

        public Heap.IHeapNode SwapDown(Heap.IHeapNode a, Heap.IHeapNode b)
        {
            var aa = a as HeapNode;
            var bb = b as HeapNode;
            System.Diagnostics.Trace.Assert(aa != null && bb != null);
            T t = List[aa.Index];
            List[aa.Index] = List[bb.Index];
            List[bb.Index] = t;
            return b;
        }

        public Heap.IHeapNode GetLastNonLeaf()
        {
            int i = Head / 2 - 1;
            return i < 0 ? null : new HeapNode(i);
        }

        public Heap.IHeapNode GetPrevNodeLinearly(Heap.IHeapNode n)
        {
            var nn = n as HeapNode;
            System.Diagnostics.Trace.Assert(nn != null);
            return nn.Index > 0 ? new HeapNode(nn.Index - 1) : null;
        }

        public Heap.IHeapNode FinishRemoval(Heap.IHeapNode p)
        {
            var pp = p as HeapNode;
            System.Diagnostics.Trace.Assert(pp != null);
            T t = List[pp.Index];
            for (int i = pp.Index; i < Head - 1; i++)
            {
                List[i] = List[i + 1];
            }
            List[Head - 1] = t;
            return new HeapNode(Head - 1);
        }

        public Heap.IHeapNode GetParent(Heap.IHeapNode n)
        {
            var nn = n as HeapNode;
            System.Diagnostics.Trace.Assert(nn != null);
            return nn.Index <= 0 ? null : new HeapNode((nn.Index - 1) / 2);
        }

        public Heap.IHeapNode GetLeft(Heap.IHeapNode n)
        {
            var nn = n as HeapNode;
            System.Diagnostics.Trace.Assert(nn != null);
            int i = nn.Index * 2 + 1;
            return i >= Head ? null : new HeapNode(i);
        }

        public Heap.IHeapNode GetRight(Heap.IHeapNode n)
        {
            var nn = n as HeapNode;
            System.Diagnostics.Trace.Assert(nn != null);
            int i = nn.Index * 2 + 2;
            return i >= Head ? null : new HeapNode(i);
        }

        public Heap.IHeapNode Root
        {
            get
            {
                return Head == 0 ? null : new HeapNode(0);
            }
        }

        public void FillHeap(Heap.IListedHeap h)
        {
            Head = List.Count;
        }

        public Heap.IHeapNode AddToHeap(Heap.IHeap h)
        {
            return Head < List.Count ? new HeapNode(Head++) : null;
        }

        public bool ExtrudeFromHeap(Heap.IHeap h)
        {
            if (Head == 0)
                return false;

            Head--;

            if (Head == 0)
                return false;

            T t = List[Head];
            List[Head] = List[0];
            List[0] = t;

            return true;
        }

        protected int Compare(Heap.IHeapNode a, Heap.IHeapNode b)
        {
            var aa = a as HeapNode;
            var bb = b as HeapNode;
            System.Diagnostics.Trace.Assert(aa != null && bb != null);
            return List[aa.Index].CompareTo(List[bb.Index]);
        }

        public void Sort()
        {
            HeapSort.Sort(this, this as HeapSort.IHeapSortAdapter, Compare);
        }

        public void Sort2()
        {
            HeapSort.Sort(this, this /* as HeapSort.IHeapSortAdapter2*/, Compare);
        }

        #endregion

        #region Fields

        protected TListOfT List;
        protected int Head;

        #endregion
    }
}
